import collections


class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        self.flag = 0


class Solution(object):
    def addBoldTag(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: str
        """
        root = Node('*')
        for word in words:
            node = root
            for i in range(len(word)):
                if word[i] in node.neighbors:
                    node = node.neighbors[word[i]]
                else:
                    new_node = Node(word[i])
                    node.neighbors[word[i]] = new_node
                    node = new_node
            node.flag = 1
        left_index = 0
        n = len(s)
        out = collections.deque()
        while left_index < n:
            if s[left_index] in root.neighbors:
                max_val = -1
                node = root.neighbors[s[left_index]]
                if node.flag:
                    max_val = 0
                right_index = left_index + 1
                while right_index < n and s[right_index] in node.neighbors:
                    node = node.neighbors[s[right_index]]
                    if node.flag:
                        max_val = max(max_val, right_index - left_index)
                    right_index += 1
                if max_val >= 0:
                    out.append([left_index, left_index + max_val])
            left_index += 1
        if not out:
            return s
        return_out = collections.deque()
        return_out.append(out[0])
        for i in range(1, len(out)):
            if out[i][0] <= return_out[-1][1] + 1:
                return_out[-1][1] = max(return_out[-1][1],out[i][1])
            else:
                return_out.append(out[i])
        t = ''
        t += s[:return_out[0][0]]
        for i in range(len(return_out)):
            if i >= 1:
                t += s[return_out[i - 1][1] + 1: return_out[i][0]]
            t += '<b>'
            t += s[return_out[i][0]: return_out[i][1] + 1]
            t += '</b>'
        t += s[return_out[-1][1] + 1:]
        return t


data = Solution()
# s = "abcxyz123"
# words = ["abc", "123"]
# print(data.addBoldTag(s, words))
# s = "aaabbcc"
# words = ["aaa", "aab", "bc"]
# print(data.addBoldTag(s, words))
s = "aaabbcc"
words = ["aaa", "aab", "bc", "aaabbcc"]
print(data.addBoldTag(s, words))
